package com.leetcode.sort;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/12/21 19:16
 */
public class FrequentSort {

    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 9, 4, 1, 4, 2};
        sort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }

    //对输入的数组按出现的频率进行排序，若出现频率一致则按数字升序排序。
    //例如：1, 2, 4, 9, 4, 1, 4, 2, 结果为：4, 4, 4, 1, 1, 2, 2, 9
    public static void sort(int[] nums, int n) {
        Map<Integer, Set<Integer>> map = new TreeMap<>((o1, o2) -> o2 - o1);
        Map<Integer, Integer> times = new HashMap<>();

        for (int num : nums) {
            int count = times.getOrDefault(num, 0);
            times.put(num, count + 1);

            if (!map.containsKey(count + 1)) {
                map.put(count + 1, new TreeSet<>());
            }
            map.get(count + 1).add(num);

            if (count != 0) {
                Set<Integer> set = map.get(count);
                if ((set.size() == 1)) {
                    map.remove(count);
                } else {
                    set.remove(num);
                }
            }
        }

        int index = 0;

        for (int count : map.keySet()) {
            Set<Integer> set = map.get(count);
            for (int num : set) {
                for (int i = 0; i < count; i++) {
                    nums[index++] = num;
                }
            }
        }
    }

}
